1. Field of the Invention
This invention relates to modulus-N residue generating circuit apparatus and more particular to circuit apparatus for generating modulus-N residues wherein N is an odd integer greater than one.
2. Description of the Prior Art
A modulus-N residue is the remainder obtained when an operand is divided by the number N. Thus, for modulus three, i.e. N=3, hereinafter referred to as modulus-3 or modulo-3 or simply mod-3, the three possible numerical values of the residues are 0, 1 and 2.
As is well known to those skilled in the art, modulus-N residues are often used as error detection codes. For example, in a modulo-3 check, which is also synonymous with residue check, an operand is divided by 3 to generate a remainder that is retained and later used for checking. If the remainder obtained when the operand is subsequently divided by 3 does not equal the retained value, an error is indicated. Residue checking logic circuits are used to detect arithmetic errors in digital computers. For example, multiplication of A and B can be checked using the following relationship: EQU Residue (A.times.B)=Residue (A).times.Residue (B).
For further information regarding error detecting logic in general and mod-3 residue checking circuits in particular, the reader is referred to, for example, "Error Detecting Logic For Digital Computers", Frederick F. Sellers, Jr. et al, McGraw-Hill Book Company, 1968, pages 76-83, 130-132.
To generate the mod-N residues heretofore, the prior art required a significant number of logic circuit components and/or a corresponding complexity. For example, one known circuit to generate the mod-3 residue of a twenty-eight bit number required one-hundred and fifty-eight And/Invert circuits and twelve stages of delay, and hence a concomitant amount of circuitry and power. Even when implemented in large scale integrated circuit technology, such as LSI or VLSI, this represents a significant hardware and real estate investment.
A type of logic, which is sometimes referred to in the art as cascode logic or cascode current switch logic, works on the principle of current steering such as, for example, the circuits described in "Multiple Level Logic Circuit", U.S. Pat. No. 3,446,989 and "Cascode Polarity Hold Latch Having Integrated Set/Reset Capability", U.S. Pat. No. 4,274,017 of the common assignee herein, and the circuits described in "High-Speed Look-Ahead Carry"--E. J. Nosowicz et al, "Scale of Two Divider"--C. S. K. Ng et al, and "Cascode Current Switch ALU"--J. H. Underwood, IBM.RTM. Technical Disclosure Bulletin, Vol. 20, No. 12, May 1978, pp 5150-5151, Vol. 21, No. 9, February, 1979, pp 3609-3611, and Vol. 21, No. 12, May 1979, pp 4808-4810, respectively, to name just a few.
However, heretofore in the prior art of which we are aware, modulus-N residue generating circuit apparatus have not been implementable and/or implemented in cascode logic; cf., for example, the integrated circuit (IC) modular modolo 3 module described in U.S. Pat. No. 4,190,893.